//============================================================================
// Name        : Bridge.cpp
// Author      : Xubin
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;
typedef vector<short> VST;
typedef stack<short> SST;

void erase_elem(VST &v, short p)
{
	VST::iterator i;
	i = find(v.begin(), v.end(), p);
	if (i != v.end())
	{
		v.erase(i);
		sort(v.begin(), v.end());
	}
}

void add_elem(VST &v, short p)
{
	v.push_back(p);
	sort(v.begin(), v.end());
}

bool findNext(stringstream &ss, VST &v, short &p1, short &p2)
{
	if (v.size() < 2)
	{
		cout << "Error: v.size() < 2" << endl;
		return false;
	}
	ss >> p1 >> p2;
	//only one of them are non-zero, error condition
	if (p1 * p2 == 0 && p1 - p2 != 0)
	{
		cout << "Error: p1 * p2 == 0 && p1 - p2 != 0" << endl;
		return false;
	}
	// both zero, simple
	if (p1 == 0 && p2 == 0)
	{
		p1 = v.front();
		p2 = *(v.begin() + 1);
		return true;
	}
	// both non-zero
	VST::iterator i;
	i = find(v.begin(), v.end(), p2) + 1;
	if (i != v.end())
	{
		p2 = *i;
	}
	else
	{
		i = find(v.begin(), v.end(), p1) + 1;
		if (i != v.end() - 1)
		{
			p1 = *i;
			p2 = *(i + 1);
		}
		else
		{
			return false;
		}

	}
	return true;
}

bool findNext(stringstream &ss, VST &v, short &p1)
{
	if (v.size() < 1)
	{
		cout << "Error: v.size() < 1" << endl;
		return false;
	}
	ss >> p1;
	//only one of them are non-zero, error condition
	if (p1 < 0)
	{
		cout << "Error: p1 < 0" << endl;
		return false;
	}
	VST::iterator i;
	if (p1 > 0)
	{
		i = find(v.begin(), v.end(), p1) + 1;
	}
	if (p1 == 0)
	{
		i = v.begin();
	}
	if (i != v.end())
	{
		p1 = *i;
	}
	else
	{
		return false;
	}
	return true;
}

void moniter(const VST &here, const VST &there, const SST &pushed,
		const stringstream &poped)
{
	cout << "1.here:" << "    ";
	VST::const_iterator i = here.begin();
	while (i != here.end())
	{
		cout << *i << ",";
		i++;
	}
	cout << endl << "2.there:" << "    ";
	i = there.begin();
	while (i != there.end())
	{
		cout << *i << ",";
		i++;
	}
	cout << endl << "3.pushed:" << "    ";
	SST backup(pushed);
	while (!backup.empty())
	{

		cout << backup.top() << ",";
		backup.pop();
	}
	cout << endl << "4.poped:" << endl << "    ";
	cout << poped.str() << endl;
}

int main()
{
	VST here, there;
	SST pushed;
	stringstream poped;

	here.push_back(1);
	here.push_back(3);
	here.push_back(6);
	here.push_back(8);
	here.push_back(12);

	short p1, p2;
	VST::iterator iv;

	while (1)
	{
		cout<<">>>>>>>>>>2:"<<endl;
		moniter(here, there, pushed, poped);//test
		// ---------- This side
		p1 = p2 = 0;
		if (findNext(poped, here, p1, p2) == false) // can't find the next step, go back
		{
			if (pushed.empty()) // can't go back anymore
			{
				cout << "pushed.empty()" << endl;
				return 1;
			}
			else
			{
				p1 = pushed.top();
				pushed.pop();
				poped.str("");
				poped << p1;
				erase_elem(here, p1);
				add_elem(there, p1);
			}
		}
		// Else go forward
		if (p2 != 0)
		{
			pushed.push(p1); // p1 < p2
			pushed.push(p2);
			erase_elem(here, p1); // erase and keep sorted
			erase_elem(here, p2);
			add_elem(there, p1); // add and keep sorted
			add_elem(there, p2);
		}
		cout<<">>>>>>>>>>1:"<<endl;
		moniter(here, there, pushed, poped);//test
		// -------- Now, the opposite side.
		p1 = p2 = 0;
		if (findNext(poped, there, p1) == false) // can't find the next step, go back
		{
			if (pushed.empty()) // can't go back anymore
			{
				cout << "impossible pushed.empty(), but it happened" << endl;
				return -1;
			}
			else
			{
				p2 = pushed.top();
				pushed.pop();
				p1 = pushed.top();
				pushed.pop();
				poped << p1 << " " << p2;
				erase_elem(there, p1);
				erase_elem(there, p2);
				add_elem(here, p1);
				add_elem(here, p2);
			}
		}
		// Else go forward
		if (p2 == 0)
		{
			pushed.push(p1); // p1 < p2
			erase_elem(there, p1); // erase and keep sorted
			add_elem(here, p1); // add and keep sorted
		}

	}
}

